%\begin{center}
%\large \bf \runtitle
%\end{center}
%\vspace{1cm}
\chapter*{\runtitle}

\noindent Eternity II is an Edge-Matching puzzle which involves to fit 256 
square puzzle pieces into a 16 by 16 grid. Released as a board game on 2007 
with a reward of two million dollars to the one able to find a solution, 
even today, as the deadline has passed, there is no known complete solution. It
has been shown that the resolution of this type of puzzle as well as other types is NP-complete. 
The work presented in this thesis describes the application of an hybrid 
metaheuristic to the Eternity II problem. We use a genetic algorithm with 
a Hill Climing type local search to which, furthermore, we add parallelism.
We analyze the benefits of the combination of both techniques, show the 
state of the art of the problem and we make a comparison of our final results 
against those reached by other authors.
\bigskip

\noindent\textbf{Keywords:} Genetic Algorithm, Eternity II, Puzzle, Local
Search, Metaheuristic.
